package basic.sort.map;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.map
 * @since JDK1.8
 *
 * 实现并查集
 */
public class DisjointSet {

    /**
     * 包装类
     * @param <V>
     */
    private static class Element<V> {
        V value;

        public Element(V value) {
            this.value = value;
        }

        @Override
        public int hashCode() {
            return 0;
        }

        public boolean equals() {
            return false;
        }
    }

    private static class UnionFind<V> {
        // 值自己的包装
        private final HashMap<V, Element<V>> elementMap;
        // 节点的父节点
        private final HashMap<Element<V>, Element<V>> fatherMap;
        // 每一个集合的大小
        private final HashMap<Element<V>, Integer> sizeMap;

        public UnionFind(List<V> values) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();

            // 记录总集合的每一个元素，以防之后判断集合时，输入了总集合之外的集合还不能发现
            for (V value : values) {
                elementMap.put(value, new Element<>(value));
            }
        }

        /**
         * 判断元素是否在同一个集合里面
         * @param a 元素a
         * @param b 元素b
         * @return 返回结果
         */
        public boolean isSameSet(V a, V b) {
            // 判断原始集合元素中是否含有需要判断的元素
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                // 有则比对两者的最顶端的父节点是否相等
                return findFather(elementMap.get(a)) == findFather(elementMap.get(b));
            }

            // 没有直接返回false
            return false;
        }

        /**
         * 合并两个元素的集合
         * @param a 元素a
         * @param b 元素b
         */
        public void union(V a, V b) {
            // 判断原始集合元素中是否含有需要判断的元素
            if (!elementMap.containsKey(a) || !elementMap.containsKey(b)) {
                return;
            }

            // 找到两元素的父节点
            Element<V> fatherA = findFather(elementMap.get(a));
            Element<V> fatherB = findFather(elementMap.get(b));

            // 如果不相等，则证明在不同的集合里面，可以合并
            if (fatherA != fatherB) {
                // 获取集合的元素个数
                int sizeA = sizeMap.get(fatherA);
                int sizeB = sizeMap.get(fatherB);

                // 找到小节点和大节点
                Element<V> small = sizeA >= sizeB ? fatherB : fatherA;
                Element<V> big = small == fatherA ? fatherB : fatherA;

                // 重新设置
                fatherMap.put(small, big);
                sizeMap.put(big, sizeA + sizeB);
                sizeMap.remove(small);
            }
        }

        /**
         * 找到一个元素的父元素
         * 同时，将查找链上的所有元素都直接指向最顶端的元素
         * @param element 目标元素
         * @return 返回找到的父元素
         */
        private Element<V> findFather(Element<V> element) {
            // 栈，用于存放链上的元素
            Stack<Element<V>> stack = new Stack<>();

            // 循环查找父元素，并记录链上每一个元素
            while (fatherMap.get(element) != element) {
                stack.add(element);
                element = fatherMap.get(element);
            }

            // 将栈中的元素一一弹出，并指向父元素
            while (!stack.isEmpty()) {
                fatherMap.put(stack.pop(), element);
            }

            return element;
        }

    }
}
